package 剑指offer.堆栈队列;

import java.util.Stack;

/**
 * 定义栈的数据结构，
 * 请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
 */
public class 第30题包含min函数的栈 {

    /*
    很简单的想法就是搞一个变量，在压栈的时候不断记录最小值就行了
    但是：他只能记录一个最小值，无法记录次小值，次次小值。。。
         且如果栈里面的最小值出栈了，该变量保存的最小值就失效了

    所以需要一个数据结构能够存储最小值、次小值、次次小值。
    一旦栈里面的最小值出栈了，就把辅助栈里面也把这个值出栈，于是辅助栈里面存储的就是剩下的数据里面的最小值


    考虑到栈弹出数据后，依然还能找到目前的最小值。需要一个辅助栈来保存最小值

     */

    static Stack<Integer> stack = new Stack<>();
    static Stack<Integer> help = new Stack<>();

    public void push(int node) {
        stack.push(node);
        if (help.empty()){
            help.push(node);
        } else {
            // 栈虽然要源源不断的压入数据，但是辅助栈只能存储比栈顶还要小的数据
            // 于是 help 栈里面存储的就是：最小、次小、次次小（从上往下看）
            if (node < help.peek())
                help.push(node);
        }
    }

    public void pop() {
        if (!stack.isEmpty() && !help.isEmpty()) {
            // 注意stack出栈的数据，小于等于 help 栈顶的时候才允许一起出栈
            if (stack.peek() > help.peek()){
                stack.pop();
            } else {
                // 当栈里面弹出的数据等于辅助栈顶的数据的时候才允许辅助栈也出栈
                // 不然只弹出辅助栈
                stack.pop();
                help.pop();
            }
        }
    }

    public int top() {
        int res = 0;
        if (!stack.isEmpty() && !help.isEmpty()) {
            res = stack.peek();
            help.peek();
        }
        return res;
    }

    public int min() {
        int res = 0;
        if (!stack.isEmpty() && !help.isEmpty()) {
            res = help.peek();
        }
        return res;
    }
}
